package com.salim.leetcode.$114;

import com.salim.leetcode.util.TreeNode;
import com.salim.leetcode.util.TreeNodeUtils;
import lombok.extern.slf4j.Slf4j;

@Slf4j
public class FlattenBinaryTreetoLinkedList {

    /**
     * 找最末位的右节点a1 然后递归往上
     * 如果父亲没有左 那继续往上 父亲->a1
     * 如果父亲有左 找到左边最末位的右节点a2 接上 a2->a1
     *
     * @param root
     */
    public void flatten(TreeNode root) {
        loop(root,null);
    }

    public TreeNode loop(TreeNode current,TreeNode child){
        //log.info("current:{},child{}",current.val,child==null?null:child.val);
        if(current==null){
            return null;
        }
        //找到右侧叶子结点 如果有父亲 接上父亲并向上返回
        if(current.left==null && current.right==null){
            if(child!=null){
                current.right = child;
            }
            return current;
        }
        if(current.right!=null){
            child = loop(current.right,child);
        }

        if(current.left==null){
            current.right = child;
            return current;
        }else{
            child = loop(current.left,child);
            current.right = child;
            current.left = null;
            return current;
        }
    }

    public static void main(String[] args){
        Integer[] arr = {1,2,5,3,4,null,6};
        TreeNode root = TreeNodeUtils.generateTreeNode(arr);
        FlattenBinaryTreetoLinkedList flattenBinaryTreetoLinkedList = new FlattenBinaryTreetoLinkedList();
        flattenBinaryTreetoLinkedList.flatten(root);
        log.info("root:{}",root);
    }
}
